import java.util.HashMap;
import java.util.Map;

/**
 * @Author：徐志荣
 * @Date：2023/9/6 上午 8:47
 */
public class Day0906 {
    public static void main(String[] args) {
        int[] fruits = {1,2,3,2,2};
        System.out.println("904. 水果成篮: "+totalFruit(fruits));
        System.out.println("904. 水果成篮: 第二种解法： "+totalFruit2(fruits));

    }

    public static int totalFruit(int[] fruits) {
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
        int  ret = 0;
        for(int left = 0,right = 0;right<fruits.length;right++){
            //进窗口
            int in = fruits[right];
            hash.put(in,hash.getOrDefault(in,0)+1);

            //判断
            while(hash.size()>2){
                //出窗口
                int out = fruits[left];
                hash.put(out,hash.get(out)-1);
                if(hash.get(out) == 0){
                    hash.remove(out);
                }
                left++;
            }
            //更新数据
            ret = Math.max(ret,right-left+1);
        }
        return ret;
    }

    /**
    * 第二种解法
    * @param fruits
    * @return
    */
    public static int totalFruit2(int[] fruits) {
        int n = fruits.length;
        int[] hash = new int[n+1];
        int  ret = 0;
        for(int left = 0,right = 0,kinds = 0;right<n;right++){
            //进窗口
            int in = fruits[right];
            if(hash[in] == 0){
                kinds++;
            }
            hash[in]++;

            //判断
            while(kinds>2){
                //出窗口
                int out = fruits[left];
                hash[out]--;
                if(hash[out] == 0){
                    kinds--;
                }
                left++;
            }
            //更新数据
            ret = Math.max(ret,right-left+1);
        }
        return ret;
    }
}
